btc utreexo - utxo accumulator

2022-09-16 ยท 2 min read

  • paper: https://eprint.iacr.org/2019/611.pdf
  • github: https://github.com/mit-dci/utreexo
  • related (2016 - delayed txo commitments): https://petertodd.org/2016/delayed-txo-commitments
  • current compressed UTXO set size ~4 GiB
  • btc full nodes would like to verify txns w/o storing full history + UTXO set (need to actually download more data though).
  • instead, build UTXO set accumulator and have transactors present inclusion proofs for their txn inputs in the UTXO set, so you (the full node) can verify the txn.
  • utreexo: use a dynamic accumulator to commit to the current UTXO set.
  • log(n): forest of perfect merkle trees. log n trees, where n is # UTXOs
  • dynamic: efficient batch removal
  • different than merkle accumulator we used for txn history in diem (a merkle mountain range (MMR)), which was append-only with efficient inclusion, non-inclusion, and batch update proofs but no removals (used jellyfish sparse merkle tree for that).
  • accumulator isn't commited to in consensus / block header / block. have to sync the whole thing from scratch lol.
  • optimizes for min. persisted space vs max. bandwidth usage.
  • per Tadge's words: "not a commitment", though you can certainly (ab)use it as one.
  • new block producer (or bridge node) can add aggregated UTXO accumulator insert/remove ops to get utreexo nodes to verify block.
  • transactors (or the full node they use to propagate) need to store the partial UTXO set accumulator, containing their UTXOs, so they can produce inclusion proofs.